package com.hjx.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.function.BinaryOperator;
import java.util.function.IntBinaryOperator;
import java.util.function.Predicate;

/**
 * 801、使序列递增的最小交换次数
 *
 * <pre>
 * 我们有两个长度相等且不为空的整型数组 A 和 B 。
 * <pre>
 * 我们可以交换 A[i] 和 B[i] 的元素。注意这两个元素在各自的序列中应该处于相同的位置。
 * <pre>
 * 在交换过一些元素之后，数组 A 和 B 都应该是严格递增的
 *    （数组严格递增的条件仅为A[0] < A[1] < A[2] < ... < A[A.length - 1]）。
 * <pre>
 * 给定数组 A 和 B ，请返回使得两个数组均保持严格递增状态的最小交换次数。
 * 假设给定的输入总是有效的。
 * <pre>
 * 示例:
 * 输入: A = [1,3,5,4], B = [1,2,3,7]
 * 输出: 1
 * 解释: 交换 A[3] 和 B[3] 后，两个数组如下:
 *
 *       A = [1, 3, 5, 7] ， B = [1, 2, 3, 4]
 *
 * 两个数组均为严格递增的。
 *
 * 注意:
 *    A, B 两个数组的长度总是相等的，且长度的范围为 [1, 1000]。
 *    A[i], B[i] 均为 [0, 2000]区间内的整数。
 * <pre>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/minimum-swaps-to-make-sequences-increasing
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author houjinxin
 * @version 创建时间：2019/9/6.
 */
public class LeetCode_801 {



    public int minSwap(int[] A, int[] B) {

        if (A.length != B.length) {
            throw new IllegalArgumentException("两数组长度必须相等");
        }
        if (!(A.length <= 1000 && A.length >= 1)) {
            throw new IllegalArgumentException("数组长度不正确");
        }

        Predicate<Integer> p1 = index -> {
            if (index == A.length - 1) {
                return B[index] > A[index -1]
                        && A[index] > B[index -1];
            } else {
                return A[index+1] > B[index]
                        && B[index] > A[index -1]
                        && A[index] > B[index -1];
            }
        };

        Predicate<Integer> p2 = index -> {
            if (index == A.length - 1) {
                return B[index-1] < A[index]
                        && A[index-1] < B[index];
            } else {
                return B[index-1] < A[index]
                        && A[index-1] < B[index]
                        && B[index] < B[index+1];
            }
        };
        Predicate<Integer> p3 = index -> {
            if (index == A.length - 1) {
                return B[index-1] < A[index-1]
                        && A[index] < B[index];
            } else {
                return B[index-1] < A[index-1]
                        && A[index] < B[index]
                        && B[index] < A[index+1];
            }
        };

        Predicate<Integer> p4 = index -> {
            if (index == A.length - 1) {
                return B[index-1] < A[index-1];
            } else {
                return B[index-1] < A[index-1]
                        && A[index+1] <= B[index];
            }
        };

        int times = 0;
        while(true) {
            int aSwapIndex = findFirstSwapIndex(A);
            int bSwapIndex = findFirstSwapIndex(B);
            int swapIndex = 0;

            if (aSwapIndex >= 0 && bSwapIndex >= 0) {
                swapIndex = Math.max(aSwapIndex, bSwapIndex);
                if (aSwapIndex < bSwapIndex){
                    swapAB(A, B);
                }
            } else if(aSwapIndex < 0 && bSwapIndex < 0){
                break;
            } else {
                if (aSwapIndex < 0) {
                    swapIndex = bSwapIndex;
                    swapAB(A, B);
                }
                if (bSwapIndex < 0) {
                    swapIndex = aSwapIndex;
                }
            }

            if (A[swapIndex-1] > A[swapIndex]) {

                if (p1.test(swapIndex)){
                    times++;
                    swap(A,B, swapIndex);
                } else if(p2.test(swapIndex)){
                    times++;
                    swap(A,B, swapIndex-1);
                }

            } else if (A[swapIndex-1] == A[swapIndex]){

                if (p3.test(swapIndex)){
                    times++;
                    swap(A,B, swapIndex);
                } else if(p4.test(swapIndex)){
                    times++;
                    swap(A,B, swapIndex-1);
                }
            }


        }

        /*
         * 六元素位置关系如下：
         *
         * A[swapIndex-1]    A[swapIndex]     A[swapIndex+1]
         * B[swapIndex-1]    B[swapIndex]     B[swapIndex+1]
         *
         * swapIndex 处的元素大小情况分为以下四种
         *
         * 当 A[swapIndex-1] > A[swapIndex] 时
         * 1、替换swapIndex处元素，变换后如下：
         *          A[swapIndex-1]    B[swapIndex]     A[swapIndex+1]
         *          B[swapIndex-1]    A[swapIndex]     B[swapIndex+1]
         *
         *    由于满足严格递增条件，推知四者大小关系为：
         *         A[swapIndex+1] > B[swapIndex] > A[swapIndex-1] > A[swapIndex] > B[swapIndex-1]
         *
         * 2、替换swapIndex-1处元素，变化后如下：
         *          B[swapIndex-1]    A[swapIndex]     A[swapIndex+1]
         *          A[swapIndex-1]    B[swapIndex]     B[swapIndex+1]
         *    由于满足严格递增条件，推知四者大小关系为：
         *          B[swapIndex-1] < A[swapIndex] < A[swapIndex-1] < B[swapIndex] < B[swapIndex+1]
         *
         * 当 A[swapIndex-1] = A[swapIndex] 时
         * 替换哪一个元素 取决于 B数组在这两个位置的值和A[swapIndex+1]的关系
         * 3、替换swapIndex处元素，变换后如下
         *          A[swapIndex-1]    B[swapIndex]    A[swapIndex+1]
         *          B[swapIndex-1]    A[swapIndex]    B[swapIndex+1]
         *
         *    由于满足严格递增条件, 推知四者关系大小
         *          B[swapIndex-1] < A[swapIndex-1] = A[swapIndex] < B[swapIndex] < A[swapIndex+1]
         *    无法判断B[swapIndex+1]和A[swapIndex+1]的关系
         *
         * 4、替换swapIndex-1处元素，变换后如下
         *          B[swapIndex-1]    A[swapIndex]    A[swapIndex+1]
         *          A[swapIndex-1]    B[swapIndex]    B[swapIndex+1]
         *    由于满足严格递增条件, 推知几者关系大小
         *          B[swapIndex-1] < A[swapIndex-1] = A[swapIndex] < A[swapIndex+1]
         *    隐含的条件为 A[swapIndex+1] <= B[swapIndex] < B[swapIndex+1]
         */


        return times;
    }

    /**
     * 倒着找到第一处不符合严格递增条件的元素的索引 i
     * 分两种情况
     * 1、交换索引为i的元素后，i 以后 两数组子数组 严格递增
     * 2、交换索引为i-1的元素后，i-1 以后 两数组子数组 严格递增
     * @param A
     * @return
     */
    public int findFirstSwapIndex(int[] A) {
        for (int i = A.length - 1; i >= 1; i--) {
            if (A[i] <= A[i - 1]) {
                return i;
            }
        }
        return -1;
    }

    public void swap(int[] a, int[] b, int index) {
        int temp = a[index];
        a[index] = b[index];
        b[index] = temp;

        System.out.println("数组A [" + Arrays.stream(a).mapToObj(String::valueOf).reduce((s, s2) -> s + "," + s2).get() + "]");
        System.out.println("数组B [" + Arrays.stream(b).mapToObj(String::valueOf).reduce((s, s2) -> s + "," + s2).get() + "]");

    }

    public void swapAB(int[] a, int[] b){
        for (int i = 0; i < a.length; i++) {
            swap(a, b, i);
        }

    }

    private boolean check(int[] a) {
        boolean isStrictlyIncreasing = true;
        for (int i = a.length - 1; i > 1; i--) {
            isStrictlyIncreasing = isStrictlyIncreasing && (a[i] > a[i - 1]);
        }
        return isStrictlyIncreasing;
    }


}
